package leetcode_201_300;

import java.util.Arrays;

public class LeeCode_233 {
    public static void main(String[] args) {
        System.out.println(countDigitOne(1000000000));
    }
    private static int countDigitOne(int n) {
        char[] s = Integer.toString(n).toCharArray();
        int len = s.length;
        int[][] memo = new int[len][len + 1];
        for (int i = 0; i < len; i++) {
            Arrays.fill(memo[i], -1);
        }
        return count(s, 0, 0, true, memo);
    }
    private static int count(char[] s, int i, int sum, boolean isLimit, int[][] memo){
        if (i == s.length){
            return sum;
        }
        if (!isLimit && memo[i][sum] != -1){
            return memo[i][sum];
        }
        int up = isLimit ? s[i] - '0' : 9, res = 0;
        for (int j = 0; j <= up; j++) {
            res += count(s, i + 1, sum + (j == 1 ? 1 : 0), isLimit && j == up, memo);
        }
        if (!isLimit)
            memo[i][sum] = res;
        return res;
    }
}
